/*
 * @lc app=leetcode.cn id=146 lang=golang
 *
 * [146] LRU 缓存机制
 */

// @lc code=start

type LRUCache struct {
	start    *DLinkNode
	end      *DLinkNode
	Cache    map[int]*DLinkNode
	capacity int
}

type DLinkNode struct {
	key, value int
	pre, next  *DLinkNode
}

func Constructor(capacity int) LRUCache {
	start := &DLinkNode{}
	end := &DLinkNode{}
	start.next = end
	end.pre = start
	return LRUCache{start, end, make(map[int]*DLinkNode), capacity}

}

func (this *LRUCache) Get(key int) int {
	if v, ok := this.Cache[key]; ok {
		v.pre.next = v.next
		v.next.pre = v.pre
		this.start.next, v.next, this.start.next.pre = v, this.start.next, v
		v.pre = this.start
		return v.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if v, ok := this.Cache[key]; ok {
		v.pre.next = v.next
		v.next.pre = v.pre
		this.start.next, v.next, this.start.next.pre = v, this.start.next, v
		v.pre = this.start
		v.value = value
	} else {
		node := &DLinkNode{key: key, value: value}
		this.start.next, this.start.next.pre, node.next, node.pre = node, node, this.start.next, this.start
		this.Cache[key] = node
		if len(this.Cache) > this.capacity {
			over := this.end.pre
			over.pre.next, this.end.pre = this.end, over.pre
			over.next, over.pre = nil, nil

			delete(this.Cache, over.key)
		}

	}
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
// @lc code=end
